package Permutation;

/**
 *
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 *
 * */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.function.Consumer;

public class Solution {
    private Integer bitMap = new Integer(0);
    public ArrayList<String> permutation(String in ){
        if("".equals(in)){
            return new ArrayList<>() ;
        }
        ArrayList<String> rs = new ArrayList<>();
        char[] cs = in.toCharArray();
        if(cs.length == 1 ){
            ArrayList<String> strings = new ArrayList<>();
            strings.add(String.valueOf(cs[0]));
            return  strings;
        }
        String str = new String();
        char pre = '1' ;
        for(int i = 0 ; i < cs.length ; i++ ){
            if(pre == cs[i]){
                str += cs[i];
                continue;
            }
            str = "" + cs[i];
            pre = cs[i];
            for(String cc : permutation(remove(cs , i))){
                rs.add(str + cc);
            }
        }
        return rs ;
    }
    public String remove(char[] array , int i ){
        ArrayList<Character> rs = new ArrayList();
        String rs1 = "";
        for(int ii = 0 ; ii < array.length ; ii++){
            if(ii != i){
                rs.add(array[ii]);
            }
        }
        for(Character c : rs ){
            rs1 += c ;
        }
        return rs1;
    }
    public String remove(char[] array , char removed){
        ArrayList<Character> rs = new ArrayList();
        String rs1 = "";
        for(char d :array){
            if(d != removed){
                rs.add(d);
            }
        }
        for(Character c : rs ){
            rs1 += c ;
        }
        return rs1;
    }
    public ArrayList<String> permutation2(String in ){
        return permutation(merge(in));
    }
    public String merge(String in ){
        StringBuilder sb = new StringBuilder();
        char[] chars = in.toCharArray();
        for(char e : chars ){
            if(!contains(e)){
                sb.append(e);
            }
        }
        return sb.toString();
    }
    public boolean contains(char c ){
        if((bitMap & c ) > 0){
           return true;
        }
        bitMap = bitMap << c ;
        return false ;
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println("--abc----------------");
//        s.permutation("abc").forEach( x ->{
//            System.out.println(x);
//        });
        System.out.println("----abcc--------------");
        s.permutation("ccab").forEach( x ->{
            System.out.println(x);
        });
//        System.out.println("--ab----------------");
//        s.permutation("ab").forEach( x ->{
//            System.out.println(x);
//        });
    }
}
